package likou;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 1062. 最长重复子串
 * <p>
 * 给定字符串 S，找出最长重复子串的长度。如果不存在重复子串就返回 0。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入："abcd"
 * 输出：0
 * 解释：没有重复子串。
 * 示例 2：
 * <p>
 * 输入："abbaba"
 * 输出：2
 * 解释：最长的重复子串为 "ab" 和 "ba"，每个出现 2 次。
 * 示例 3：
 * <p>
 * 输入："aabcaabdaab"
 * 输出：3
 * 解释：最长的重复子串为 "aab"，出现 3 次。
 * 示例 4：
 * <p>
 * 输入："aaaaa"
 * 输出：4
 * 解释：最长的重复子串为 "aaaa"，出现 2 次。
 * <p>
 * 链接：https://leetcode-cn.com/problems/longest-repeating-substring
 *
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/11/30 14:05
 */
public class _1062 {
    public static void main(String[] args) {
        _1062 one = new _1062();
        System.out.println(one.longestRepeatingSubstring("abbaba"));
    }

    public int maxHeight(int[][] cuboids) {
        // 首先，将各个长方体数组内部的元素（即边长）从小到大进行排序
        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }
        // 随后将整个长方体数组按照最短边长、次长边长、最长边长进行排序
        Arrays.sort(cuboids, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return Integer.compare(o1[0], o2[0]);
            } else if (o1[1] != o2[1]) {
                return Integer.compare(o1[1], o2[1]);
            } else {
                return Integer.compare(o1[2], o2[2]);
            }
        });
        // dp[i]表示【以第i个长方体为底】的【堆叠长方体】的最大高度
        int[] dp = new int[cuboids.length];
        int maxAns = 0;
        // 显然，我们需要找出可以放在第i个长方体上方的所有【堆叠长方体】的最大高度
        // 加上第i个长方体的高度，就可以得出【以第i个长方体为底】的【堆叠长方体】的最大高度
        for (int i = 0; i < cuboids.length; i++) {
            for (int j = 0; j < i; j++) {
                // 虽然我们已经做了排序，但是还不能保证前面的长方体一定能够放在后面的长方体上方，只能保证后面的长方体一定不能放在前面的长方体上
                // 因此需要依次进行判断前面各个【堆叠长方体】能不能放置在第i个长方体上方，并找出前面各个【堆叠长方体】的最大高度的【最大值】
                if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
                    dp[i] = Math.max(dp[i], dp[j]);
                }
            }
            dp[i] += cuboids[i][2];
            // 更新所有【堆叠长方体】的最大高度
            maxAns = Math.max(maxAns, dp[i]);
        }
        return maxAns;
    }

    public int search(int L, int n, String S) {
        HashSet<String> seen = new HashSet();
        String tmp;
        for (int start = 0; start < n - L + 1; ++start) {
            tmp = S.substring(start, start + L);
            if (seen.contains(tmp)) return start;// 存在两个相等的区间
            seen.add(tmp);
        }
        return -1;
    }

    public int longestRepeatingSubstring(String S) {

        int n = S.length();
        int left = 1, right = n;
        int L;
        while (left <= right) {
            L = left + (right - left) / 2;// 二分，L是子串的长度
            if (search(L, n, S) != -1) left = L + 1;
            else right = L - 1;
        }
        return left - 1;
    }
}
